﻿#include <iostream>
#include <vector>
#include <string>

using namespace std;
// 在start--end 范围内，偷窃的最高金额
int robRange(vector<int>& nums, int start, int end)
{
	int first = nums[start];
	int second = max(nums[start], nums[start + 1]);
	for (int i = start + 2; i <= end; i++)
	{
		int temp = second;
		second = max(first + nums[i], second);
		first = temp;
	}
	return second;
}
int rob(vector<int>& nums) 
{
	// n==1,直接偷
	// n==2，比较两个哪个大偷
	// n>2,
	// 1、偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。
	// 2、不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。
	int n = nums.size();
	if (n == 1)
	{
		return nums[0];
	}
	if (n == 2)
	{
		return max(nums[0], nums[1]);
	}
	return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}

//int rob(vector<int>& nums) 
//{
//	// n==1,直接偷
//	// n==2，比较两个哪个大偷
//	// n>2,
//	// 1、偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。
//	// 2、不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。
//	int n = nums.size();
//	vector<int> dp(n + 1, 0);
//	dp[0] = nums[0];
//	dp[1] = max(nums[0], nums[1]);
//
//	for (int i = 2; i < n; i++)
//	{
//		dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
//	}
//	return dp[n - 1];
//}
int rob(vector<int>& nums)
{
	// n==1,直接偷
	// n==2，比较两个哪个大偷
	// n>2,
	// 1、偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。
	// 2、不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。
	int n = nums.size();
	int first = nums[0];
	int second = max(nums[0], nums[1]);

	for (int i = 2; i < n; i++)
	{
		int temp = second;
		second = max(first + nums[i], second);
		first = temp;
	}
	return second;
}
int main()
{
	vector<int> v = { 1,3,100 };
	cout << rob(v) << endl;
	return 0;
}